1. Field of the Invention
The present invention pertains to data traffic management and in particular to data traffic policers.
2. Background Information
Packet-based data communication is a technique in which information at the source is formed into packets and transmitted through a medium, and at the destination, the packets are reassembled back to their original form. Each packet usually has a pay-load such as data, voice, image or any other type of information. Packet-based trafficking is very suitable for use in a network in that other than the particular time interval in which the network resources are dedicated to the transmission of the packet, the remaining time period is available for other packets to be transmitted. This time sharing arrangement along with the flexibility and speed of transmitting integrated information makes packet-based communication the standard method of communication used in the Internet.
Resources generally available to an Internet Service Provider (ISP) are limited. There is only a limited amount of bandwidth in which the ISP can channel packets through a network. Typically, an ISP used by a source station sends packets through the network to an ISP used by a destination station. A path through the worldwide Internet is typically supplied by a backbone provider. Within the network, a plurality of network devices (nodes) are connected together to forward the packets until eventually they arrive at their destination at an end station such as a client computer or a server. A node may be a router that processes and routes received packets to their appropriate destination. A router usually has multiple ingress/egress ports through which packets are channeled in and out of the router. Because a router is only able to process a finite number of packets at a given time, when the traffic exceeds this bandwidth, congestion usually occurs. Often this congestion occurs at a border to an ISP, although congestion may also occur internal to the network. Congestion is usually alleviated by “dropping” packets. For instance, if a router receives more packets than it can handle, it simply “drops” the incoming packets until it regains the capacity to handle the packets. If the communication protocol used is the Transmission Control Protocol (TCP), the sending node is usually notified when a packet is received (ACK message) and times out when it does not receive an ACK because a packet was dropped. Timing out usually causes the sending node to transmit the packets at a lower transmission rate. Because the transmission is duplicated for the lost packets, there occurs a higher consumption of the already limited bandwidth and a further deterioration in the efficacy of the network. Furthermore, the retransmitted packets are delivered late, if at all, slowing down the interchange of information.
From the ISP's point of view, it is desirable to manage the network so as to provide a better and a more predictable service in terms of bandwidth, latency and loss characteristics. In many instances and for various reasons, a user and the ISP will enter into a “traffic contract” that sets forth a rate in which the user may transmit data to the ISP's network. The term “traffic contract” is used to mean any agreement or decision that traffic through a particular network device is to be limited to a rate less than the wire rate, where the wire rate is the maximum rate which the physical interconnection can deliver. For example, the traffic contract may be between a customer and an ISP to limit the rate which the customer delivers packets (or bytes) to the ISP, or the rate at which the ISP delivers packets to the customer. Further, the traffic contract may be used in an enterprise network in order to limit certain types of traffic into or out of the network, for example between hosts and “the network” in order to meet traffic engineering goals. In the enterprise network example, there is no “contract” between an end user and someone else, the contract is simply how the network is set up. As a further example, a traffic contract may be involved in setting up a quality of service (QoS) arrangement with an end user. As a further example, the traffic contract rate may be to set a limit on the amount of traffic which gets special treatment in the network, or just to limit the amount of traffic in general. Also, the ISP may have a traffic contract with the provider of the network back-bone. It is usually the burden of the user to shape the traffic to meet the contracted rate. However, the ISP, the backbone (or forwarder) provider, the customer, the parts of an enterprise network, etc. may place a “policer” at ports of his exit nodes to enforce the contract.
The policer monitors its incoming packets to determine if they conform to the contract. If a packet is non-conforming (i.e., exceeds the contract rate), the policer may simply “drop” the packet. In many non-ideal implementations, a policer may be implemented to drop packets in a manner that is similar to that of a “tail-drop” in a traffic congestion situations. Tail-dropping occurs when a node is not able to handle any more incoming packets. For example, a queue simply fills up from a burst and drops all later arriving packets. A disadvantage pertaining to tail dropping is that it is very unfair. Stated differently, different connections may not have their packets dropped proportionally according to their usage. It is desirable to have a traffic policing method which does not do “tail dropping”.
On a different note, one known traffic-policing algorithm is the “leaky bucket” algorithm (for example as used in the Asynchronous Transfer Mode (ATM) Protocol, and as described in the ATM Forum's Traffic Management Specification Version 4.1). ATMs forward fixed size packets known as “cells.” A continuous-state leaky bucket algorithm, as its name implies, can be imagined as a finite-capacity bucket (actually a queue or a counter) in which a real-valued content drains out at a continuous rate of 1 unit of content per time-unit and whose content is increased by the increment 1 for each conforming cell. The leaky bucket algorithm is fully described by Andrew S. Tanenbaum in his book Computer Networks, Third Edition, published by Prentice Hall, Copy-right date 1996, all disclosures of which are incorporated herein by referenced, particularly at pages 380–381. As shown in FIG. 1, at block 100, the algorithm is activated when a cell is received. At its initiating state, the content of the bucket is zero. With the arrival of the first cell ta(1), the Last Conformance Time (LCT) is set to ta(1). With the successive arrival of the cells such as the kth cell at time ta(k), at block 102, the content of the bucket x′ is updated to equal to the value of the leaky bucket at the arrival of the last conforming cell minus the amount the bucket has drained since that arrival. Note that the content of the bucket can-not be less than zero and at blocks 104–106, if the content of the bucket x′ is less than zero, the value x′ is adjusted to zero. At block 108, if the value x′ is greater than a limit value L, the cell is non-conforming and at block 110, the values of x′ and LCT remain unchanged. Otherwise if the value x′ is less than or equal to the limit value L, the cell is conforming and at block 112, the bucket content x is set to x′ plus the increment 1 for that current cell and the LCT is set to ta(k). Further details may be found in the forum paper specified above.
The leaky bucket algorithm described above, however, tail drops “bursts” that may occur in traffic. The bucket fills, and before it empties more packets arrive because of the burst. After the bucket fills, all subsequent packets are simply discarded since they arrive faster than the bucket empties.
In another known example, a dual-leaky bucket is used to accommodate for the data bursts. The first leaky bucket polices the cells for conformance to the sustained cell rate as agreed in the contract. The second leaky bucket polices the cells for compliance with the maximum burst size allowable by the contract. Besides the leaky bucket approach, other approaches may be used such as the virtual scheduling algorithm using theoretical arrival time (TAT) also described in the forum paper. However, the virtual scheduling algorithm, too, suffers the drawbacks of tail dropping in bursty traffic.
There is needed a traffic policer which drops packets from flows in proportion to the amount of bandwidth used by the flows so that the dropping is fair, and also which does not tail drop when receiving bursty flows.